package leetcode每日一题.leetcode20213;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Stack;

/**
 * 1. 问题描述
 *
 * 2. 算法分析
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class Q005_用栈模拟队列 {
    /**
     * 采用双栈模拟队列
     * 一个栈实现入队
     * 一个栈实现出队
     *
     * 空间复杂度为O(n) 额外多使用了两个栈来模拟
     * push操作的时间复杂度为O(1)
     * pop和peek操作的时间复杂度为O(n)
     * empty操作的时间复杂度为O(1)
     */
    class MyQueue1 {

        // 队列：先进先出
        // 栈：先进后出
        Deque<Integer> stackPush;
        Deque<Integer> stackPop;
        int front; // 永远指向当前队列的队首元素

        /** Initialize your data structure here. */
        public MyQueue1() {
            stackPush = new ArrayDeque<>();
            stackPop = new ArrayDeque<>();
        }

        /** Push element x to the back of queue. */
        public void push(int x) { // 时间 O(1)  空间 O(n)
            // 如果当前队为空，将x复给front
            if(stackPush.isEmpty()) {
                front = x;
            }
            // 如果不空，说明front已经指向了当前队列的队首元素
            // 直接让x入栈到stackPush
            stackPush.push(x);
        }

        /** Removes the element from in front of queue and returns that element. */
        public int pop() { // O(n)
            // 虽然此时front记录的是当前最先进入队的元素，但是该元素在stackPush栈的栈底
            // 所以我们先将stackPush中的元素入栈到stackPop中，此时stackPop中的栈顶元素就是当前删除的队首元素
            // 如果当前stackPop为空
            if(stackPop.isEmpty()) {
                while(!stackPush.isEmpty()) {
                    stackPop.push(stackPush.pop());
                }
            }
            return stackPop.pop();
        }

        /** Get the front element. */
        public int peek() { // O(n)
            // 如果stackPop不空，则stackPop的栈顶元素就是队首元素
            if(!stackPop.isEmpty()) {
                return stackPop.peek();
            }
            // 如果stackPop为空，则front记录的就是队首元素
            return front;
        }

        /** Returns whether the queue is empty. */
        public boolean empty() { // O(1)
            return stackPush.isEmpty() && stackPop.isEmpty();
        }
    }

    /**
     * 优化上述的算法实现，将所有的操作的平均时间复杂度控制在O(1)(这是面试官想要的答案，如果没有限制，这道题还是非常简单的)
     * 主要在push做优化，因为pop和peek操作基本可以看成一个，如何push到栈中保证平均时间复杂度为O(1)
     *  首先我们需要清楚stackPush的职责就是输入，stackPop的职责就是负责输出，由于栈是先进后出的特点，而队列是线进行先出
     *  所以如果此时像要出队尾元素(队尾进，队头出)了所以需要将输入栈中的元素输出到输出栈中，但是不是什么时候都输入，只有当
     *  输出栈为空的时候，说明此时之前的输入的元素都输出，所以这样如果之后没有输入操作。只需要O(1)就可以实现pop和peek操作
     *  而输入操作为O(n),因为在输入操作中我们需要判断输出栈是否为空如果不为空。将输入栈中的元素输出到输出栈中
     */
    class MyQueue2 {

        Stack<Integer> stackPush; // 入栈
        Stack<Integer> stackPop; // 出栈

        /** Initialize your data structure here. */
        public MyQueue2() {
            stackPush = new Stack<>();
            stackPop = new Stack<>();
        }

        /** Push element x to the back of queue. */
        public void push(int x) {
            stackPush.push(x);
        }

        /** Removes the element from in front of queue and returns that element. */
        public int pop() {
            if (stackPop.isEmpty()) {
                this.StackPushToStackPop();
            }
            return stackPop.pop();
        }

        /** Get the front element. */
        public int peek() {
            if (stackPop.isEmpty()) {
                this.StackPushToStackPop();
            }
            return stackPop.peek();
        }

        /** Returns whether the queue is empty. */
        public boolean empty() {
            return stackPop.isEmpty() && stackPush.isEmpty();
        }

        public void StackPushToStackPop() {
            while (!stackPush.isEmpty()) {
                stackPop.push(stackPush.pop());
            }
        }
    }
}
